package com.example.sorts13.sort;

/**
 * @description 基数排序
 * @auther lijiewei
 * @date 2021/9/3 11:01
 */
public class RadixSort {

    /**
     * 基数排序,对于多位非负整数
     * @param arr 数组
     * @return
     * @author lijiewei
     * @date   2021/9/3 11:02
     */
    public static void redixSort(int[] arr) {
        //获取数组中最大值
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        //从个位开始，对数组arr按指数排序
        for (int exp = 1; max/exp >0 ; exp*=10) {
            countingSort(arr, exp);
        }
    }

    /**
     * 计数排序-对数组按照“某个位数”进行排序
     * @param arr 数组
     * @param exp 指数
     * @return
     * @author lijiewei
     * @date   2021/9/3 11:15
     */
    private static void countingSort(int[] arr, int exp) {
        if (arr.length <= 1) {
            return;
        }
        //计数排序
        //计算每个元素的个数
        int[] countArr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            countArr[(arr[i]/exp)%10]++;
        }
        //累加
        for (int i = 1; i < countArr.length; i++) {
            countArr[i] = countArr[i-1]+countArr[i];
        }
        //临时数组tmp存放排序后结果
        int[] tmp = new int[arr.length];
        for (int i = arr.length-1; i >=0; i--) {
            tmp[countArr[(arr[i]/exp)%10]-1] = arr[i];
            countArr[(arr[i]/exp)%10]--;
        }
        //拷贝
        for (int i = 0; i < tmp.length; i++) {
            arr[i] = tmp[i];
        }
    }
}
